﻿#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
int main()
{
    int k;
    scanf("%d", &k);
    while (k--) {
        int n, x;
        scanf("%d", &n);
        int i = 2;
        while (1) {
            int a[20] = { 0 };
            int l = 0, j = 0, len = 0;
            x = n;
            while (x > 0) {
                a[j++] = x % i;
                x /= i;
                len++;
            }
            for (l = 0; l < len / 2; l++) {
                if (a[l] != a[len - l - 1])
                    break;
            }
            if (l < len / 2)
                i++;
            else
                break;
        }
        printf("%d\n", i);
    }
    return 0;
}
/*
题目描述
回文数是指一个没有前导0的数，从左到右的数码和从右到左的数码是一样的。比如说10进制下的"121"，这就是一个回文数。

我们将这个概念扩展到b进制，n=∑ki=0ai⋅bi，其中0≤ai<b,2≤b,ak>0，如果数列ak,ak−1,…,a0构成一个回文序列，那么就称n在b进制下是回文数。比如，5在2进制下是101(2)，所以5在2进制下是回文数。

我们想知道n在b进制下为回文数时，最小的b是多少？

输入
第一行是一个整数T(1≤T≤1000)，表示样例的个数。

每个样例是一个十进制整数n(1≤n≤106)。

输出
依次每行输出一个样例的结果，为一个整数，表示b。

样例输入
2
5
6
样例输出
2
5
*/